package LeetCodeHot100TopInterview;


public class Q234_IsPalindromeLink {
    //判断回文链表 ==> manacher? ==> [判断] ==> 双指针
    //nono 没有双指针也要创造双指针
    //找到中点 ==> 逆序后半部分 ==> 双指针
    public boolean isPalindrome(ListNode head) {
        if (head == null){
            return false;
        }
        //找到下中点 其后的逆序
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 此时 slow 是 奇数-正常中点  偶数下中点
        // 此后链表进行翻转
        ListNode cur = slow.next;
        ListNode pre = slow;
        ListNode next = null;
        slow.next = null;
        while (cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        while (pre != null){
            if (head.val != pre.val){
                return false;
            }
            head = head.next;
            pre = pre.next;
        }

        return true;
    }

    public static void main(String[] args) {
        Q234_IsPalindromeLink fun = new Q234_IsPalindromeLink();
        ListNode root = new ListNode(1);
//        root.next = new ListNode(1);
//        root.next.next = new ListNode(1);
//        root.next.next.next = new ListNode(1);
        System.out.println(fun.isPalindrome(root));
    }
}
